import sys

#This file used for testing ideas

#clearly some dynamic programming is required. is it enough to track the lis
# up to the current point in the list then for the current element, add it to 
# each subsequence for which it is greater than the last element? No, because 
# it may be best for the lis to exclude a large element so that smaller elements
# later in the list can be included.
# Possible approaches:
# 1. Divide the list into two parts. Compute all increasing subsequences on each
#    then try every combination. A list with n elements may have 2^n different
#    like a poor choice (merging two 2^n candidate lists => exponential time, 
#    obviously)
# 2. The above approach illustrates the fundamental problem here. If we start at
#    the beginning of the list, and for each subsequent element, choose whether
#    or not to include it in each subsequence we have constructed so far, there
#    are 2^n possible choices. So we need to find a way to eliminate whole 
#    sequences and exclude them from future consideration. What if we compute 
#    for each i,j, the lis including only elements between i and j (inclusive).
#    Start by filling in the diagonal where i=j. then move to the next diagonal
#    over and compute j = i+1. Each element can be computed by considering all
#    of the longest increasing subsequences for the O(n^2) subranges, and adding
#    the current element if possible. Total running time would be O(n^3) 
def lis(list):
    M = [[] for i in range(len(list))]

    for i in range(len(list)):
        M[i][i] = [list[i]]

    for offset in range(1, len(list)):
        for i in range(len(list) - offset):
            j = i+offset
            # compute M[i][i+offset]
            bestCandidate = [0]
            bestCandidateLen = 0
            for innerOffset in range(offset-1):
                for ii in range(i, 1 + offset - innerOffset):
                    jj = ii + innerOffset
                    candidate = M[ii][jj]
                    candidateLen = len(candidate)
                    if list[j] > candidate[-1]:
                        candidate




if __name__ == '__main__':
    seq = []
    if len(sys.argv) > 1:
        for item in sys.argv[1:]:
            seq.append(int(item))
    else:
        seq = [4,12,6,2,8,9,7,14]
    
    print("for example, on input:") 
    print(seq)
    print("lis returns:")
    print(lis(seq))